class Solution(object):
    def maxDistance(self, arrays):
        """
        :type arrays: List[List[int]]
        :rtype: int
        """
        max_val = [(arrays[0][-1], 0), (arrays[1][-1], 1)]
        min_val = [(arrays[0][0], 0), (arrays[1][0], 1)]
        max_val.sort()
        min_val.sort()
        n = len(arrays)
        for i in range(2, n):
            min_val.append((arrays[i][0], i))
            max_val.append((arrays[i][-1], i))
            min_val.sort()
            max_val.sort()
            min_val.pop()
            del max_val[0]
        if min_val[0][1] != max_val[1][1]:
            return max_val[1][0] - min_val[0][0]
        else:
            return max(max_val[0][0] - min_val[0][0], max_val[1][0] - min_val[1][0])


data = Solution()
arrays = [[1, 2, 3],
          [0, 5],
          [1, 2, 3]]
print(data.maxDistance(arrays))
